1. Field of the Invention
The present invention relates to a system and method for effecting long impulse response filtering.
2. Description of the Related Art
With the development of new technologies, such as voice over IP (VoIP), spatial sound processing and teleconferencing, long impulse response systems are employed to obtain relatively high accuracy and better performance. For example, the length of a network echo cancellation filter can be as long as 128 mn. Therefore, 1024 filter taps can be made at a frequency of 8 kHz.
Long impulse response filtering may be effected by using direct convolution or transform methods. U.S. Pat. No. 5,502,747 describes a method and apparatus for filtering using a combination of these two methods. By this method, filtering latency and computational complexity may be reduced.
In FIG. 1, a digital filter 1 uses a convolution method in accordance with equation (1) where N denotes the length of the digital filter 1. The digital filter 1 convolves an input data sequence {x(n), 0≦n<N} with the impulse response of the digital filter {(j), 0≦j<N} to produce an output y(n).
                              y          ⁡                      (            n            )                          =                              ∑                          j              =              0                                      N              -              1                                ⁢                                    h              ⁡                              (                j                )                                      ⁢                          x              ⁡                              (                                  n                  -                  j                                )                                                                        (        1        )            
As each new input data sample, x(n), arrives, the digital filter 1 will be able to determine the corresponding output, y(n). The output will be calculated after N multiplication and addition operations, however, if N is large the output of the digital filter 1 will be delayed by the heavier computational load.
Alternatively, in FIG. 2 a method for a digital filter using a 2N-point transform method to filter a current input data sequence is shown. A 2N-point transform method buffers, for example, N data samples from the previous input data sequence, where the previous input data sequence is denoted by {x(n), 0≦n<N}. The current input data sequence is appended to the buffered data samples to form a sequential block of 2N data samples, where the data samples from the current input data sequence are denoted by {x(n), N≦n<2N}. The block of 2N data samples is then converted to the frequency domain by equation (2).
                                          X            ⁡                          (              k              )                                =                                    ∑                              n                =                0                                                              2                  ⁢                  N                                -                1                                      ⁢                                          x                ⁡                                  (                  n                  )                                            ⁢                              W                                  2                  ⁢                  N                                nk                                                    ⁢                                  ⁢        where        ⁢                                  ⁢                              W                          2              ⁢              N                        nk                    =                      ⅇ                                          2                ⁢                Π                ⁢                                                                  ⁢                nk                                            2                ⁢                N                                                                        (        2        )            
The impulse response of the filter, {h(n)}, is also converted into the frequency domain using a transform method in accordance with Equation (3).
                              H          ⁡                      (            k            )                          =                              1                          2              ⁢              N                                ⁢                                    ∑                              n                =                0                                                              2                  ⁢                  N                                -                1                                      ⁢                                          h                ⁡                                  (                  n                  )                                            ⁢                              W                                  2                  ⁢                  N                                nk                                                                        (        3        )            
The corresponding outputs of the digital filter may then be calculated using an IFT (inverse Fourier transform) given by Equation (4), where only the latest N samples, {y(n), n=N, . . . , 2N−1}, are required since only these samples reflect the response of the filter to the current input data sequence. The remaining output samples, {y(n), n=0, . . . , N−1}, are discarded.
                              y          ⁡                      (            n            )                          =                              1                          2              ⁢              N                                ⁢                                    ∑                              k                =                0                                                              2                  ⁢                  N                                -                1                                      ⁢                                          H                ⁡                                  (                  k                  )                                            ⁢                              X                ⁡                                  (                  k                  )                                            ⁢                              W                                  2                  ⁢                  N                                                  -                  nk                                                                                        (        4        )            
This method is usually used to calculate a number of outputs, N, in a block. On average, the 2N-point transform method has a low computational load, however, the method has a flow through delay of N samples which is introduced because the current input must accrue to form the above mentioned 2N data block.
If N is a power of 2 and a real data FFT (fast Fourier transform) method is used, 2N log22N real multiplications are required to calculate the 2N-point FFT of an input sequence as given by equation (2). Similarly, 2N log22N real multiplications will be required to calculate the 2N-point IFT (inverse Fourier transform) of the frequency domain products given by equation (4) and 4N real multiplications will be required to calculate the frequency domain products (H(K)*X(K)). Therefore, the average number of multiplications per sample may be estimated by equation (5), where the number of multiplications per sample is proportional to log (N).4 log24N  (5)